package lib

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

type Point struct {
	i    int
	j    int
	step int
}

// 遍历的方向
var dirs = [4]Point{
	{
		-1, 0, 0,
	},
	{
		0, -1, 0,
	},
	{
		1, 0, 0,
	},
	{
		0, 1, 0,
	},
}

func PointAdd(a, b Point) Point {
	return Point{
		a.i + b.i,
		a.j + b.j,
		0,
	}
}

func PintEq(a, b Point) bool {
	return a.i == b.i && a.j == b.j
}

// 开始走迷宫
func Walk(maps [][]int, start, end Point) [][]int {
	// fmt.Println(maps, start, end)
	// stepsPath 从start开始走了几步到了这个格子
	stepsPath := make([][]int, len(maps))
	for i, _ := range maps {
		stepsPath[i] = make([]int, len(maps[i]))
	}

	stepsPath[start.i][start.j] = 1

	//fmt.Println(len(stepsPath), len(stepsPath[0]))

	//fmt.Println(stepsPath)

	//fmt.Println(maps[end.i][end.j], stepsPath[end.i][end.j])
	//fmt.Println(end)

	// 待探索的队列
	Q := []Point{
		start,
	}

	// 探索点非空的时候才继续走
	for len(Q) > 0 {
		// 因为探索可用的路基是上左下右来的所以队列头结点是按照这个顺序来的
		currHead := Q[0]
		Q = Q[1:]

		//// 如果到了最后一个点或者范围之外直接干死
		//if currHead.i > end.i || currHead.j > end.j {
		//	break
		//}
		// fmt.Println(currHead)
		// 当前的结点要按照上 右 下 左的顺序来探索 探索四个方向
		for _, v := range dirs {
			// 新发现的结点 = 当前结点加方向
			next := PointAdd(currHead, v)

			// 如果探索的这个点是边界外边或者被探索过或者是1就是不让走就扔了
			if next.i > -1 && next.j > -1 && next.i <= end.i && next.j <= end.j {
				// 非边界外的值
				// 获取被探索的这个点是不是可用是不是1是1不让走
				// 获取让不让走地图是上不是1
				cnext := maps[next.i][next.j]
				if cnext == 0 { // 这个点是可以走的
					// 判断是不是存储过
					if stepsPath[next.i][next.j] == 0 {
						// 没有走回头路这个点合法
						// fmt.Println(next)
						Q = append(Q, next)
						stepsPath[next.i][next.j] = stepsPath[currHead.i][currHead.j] + 1
					}
				}
			}
		}
		// 走过的结点
		//stepsPath[currHead.i][currHead.j] = currHead.i + currHead.j + 1
	}
	return stepsPath
}

// 获取地图
func GetMap(path string) [][]int {
	var rt [][]int
	file, err := os.Open("/Users/apple/go/src/golearnpro/基本语法/goroute/guangduyouxian/lib/mg.txt")
	defer file.Close()

	if err != nil {
		panic(err)
	}

	buf := bufio.NewScanner(file)

	// 上来先取出一行来
	// 优化算法用
	//fmt.Fscanf(file, "%d, %d", &xxx, &xxx)
	if buf.Scan() {
		rsInfo := strings.Split(buf.Text(), " ")
		left, _ := strconv.Atoi(rsInfo[0])
		right, _ := strconv.Atoi(rsInfo[1])

		rt = make([][]int, left)
		for i := 0; i < left; i++ {
			rt[i] = make([]int, right)
		}
	}

	for i := 0; buf.Scan(); {
		rsInfo := strings.Split(buf.Text(), " ")

		for k, v := range rsInfo {
			sl, _ := strconv.Atoi(v)
			rt[i][k] = sl
		}

		i++
	}

	return rt
}

func Mg() {
	list := GetMap("mg.txt")
	// 按照 c 的流程来做这段程序
	lk := Walk(list, Point{
		0, 0, 0,
	}, Point{
		len(list) - 1, len(list[0]) - 1, 0,
	})

	// fmt.Println(lk)

	// 最短路径
	mps := make(map[int]string)
	flg := lk[len(lk)-1][len(lk[0])-1]
	a := func() {
		// 打印最短路径
		for i := len(lk) - 1; i > -1; i-- {
			for j := len(lk[i]) - 1; j > -1; j-- {
				if mps[lk[i][j]] == "" && lk[i][j] != 0 {

					if flg-lk[i][j] > 1 {
						continue
					}
					flg = lk[i][j]
					mps[flg] = fmt.Sprintf("%d,%d", i, j)

				}
			}
		}
	}

	lock := 0
	for {
		a()
		if mps[1] == "0,0" || lock == 10000 {
			break
		}

		lock++
	}

	fmt.Println(mps)
	fmt.Println(lk)
}
